package base;

/**
 * https://leetcode-cn.com/problems/longest-palindromic-subsequence
 *
 * @author mazouri
 * @create 2021-12-27 9:24
 */
public class _1_lps {
    /**
     *
     * @param s 字符串
     * @param i  左
     * @param j  右
     * @return  该字符串最长子序列数
     */
    public int lps(String s,int i,int j) {
        //只有一个字符，肯定为1呀,本身就是回文结构
        if(i == j) return 1;
        //错误的i
        if (i>j) return 0;

        //最左边和最右边的字符相等
        if (s.charAt(i) == s.charAt(j)) return lps(s,i+1,j-1)+2;
        else return Math.max(lps(s,i,j-1),lps(s,i+1,j));
    }

    public static void main(String[] args) {
        _1_lps o = new _1_lps();
        System.out.println(o.lps("bbadadbd", 0, 7));
    }
}
